// Copyright (C) 2002-2008 Nikolaus Gebhardt
// This file is part of the "Irrlicht Engine".
// For conditions of distribution and use, see copyright notice in irrlicht.h

#ifndef __HEAPSORT_H_INCLUDED__
#define __HEAPSORT_H_INCLUDED__


//! Sinks an element into the heap.
template<class T>
inline void EzHeapsink(T*array, int element, int max)
{
	while ((element<<1) < max) // there is a left child
	{
		int j = (element<<1);

		if (j+1 < max && array[j] < array[j+1])
			j = j+1; // take right child

		if (array[element] < array[j])
		{
			T t = array[j]; // swap elements
			array[j] = array[element];
			array[element] = t;
			element = j;
		}
		else
			return;
	}
}



//! Sorts an array with size 'size' using EzHeapsort.
template<class T>
inline void EzHeapsort(T* array_, int size)
{
	// for EzHeapsink we pretent this is not c++, where
	// arrays start with index 0. So we decrease the array pointer,
	// the maximum always +2 and the element always +1

	T* virtualArray = array_ - 1;
	int virtualSize = size + 2;
	int i;

	// build heap

	for (i=((size-1)/2); i>=0; --i)
		EzHeapsink(virtualArray, i+1, virtualSize-1);

	// sort array
	for (i=size-1; i>=0; --i)
	{
		T t = array_[0];
		array_[0] = array_[i];
		array_[i] = t;
		EzHeapsink(virtualArray, 1, i + 1);
	}
}

template<class T, class _Fn1>
inline void EzHeapsort(T* array_, int size, _Fn1 _Func)
{
	// for EzHeapsink we pretent this is not c++, where
	// arrays start with index 0. So we decrease the array pointer,
	// the maximum always +2 and the element always +1

	T* virtualArray = array_ - 1;
	int virtualSize = size + 2;
	int i;

	// build heap

	for (i=((size-1)/2); i>=0; --i)
		EzHeapsink(virtualArray, i+1, virtualSize-1, _Func);

	// sort array
	for (i=size-1; i>=0; --i)
	{
		T t = array_[0];
		array_[0] = array_[i];
		array_[i] = t;
		EzHeapsink(virtualArray, 1, i + 1);
	}
}


template<class T,  class _Fn1>
inline void EzHeapsink(T*array, int element, int max, _Fn1 _Func)
{
	while ((element<<1) < max) // there is a left child
	{
		int j = (element<<1);

		if (j+1 < max && _Func(array[j], array[j+1]) > 0)
			j = j+1; // take right child

		if (_Func(array[element], array[j]) > 0)
		{
			T t = array[j]; // swap elements
			array[j] = array[element];
			array[element] = t;
			element = j;
		}
		else
			return;
	}
}



#endif

